#encoding: utf-8

from constants import *
from camino import Camino_aumentante
from flujo import Flujo
import sys
import copy


class EstadoEK():
    def __init__(self, verbosidad):
        """Matriz donde guardamos los lados y su capacidad.
           Al final quedará algo así: {0: {1:.., 2:66}, ..., 4: {5:6,..},...}
           ie: la capacidad del lado xy está en matriz[x][y]
        """
        if not self.__verb_correcta(verbosidad):
            print "Error: la verbosidad no es correcta.\n"
            sys.exit(1)

        self.matriz = {}
        self.gamamenos = {}
        self.verbosidad = verbosidad

    def leer_un_lado(self):
        """Leemos un lado desde el stdin en la forma x y c, donde xy es lado
        y c es la capacidad. Devuelve 1 en caso de éxito. Si encuentra un EOF
        o algo que no es un lado devuelve 0"""
        termino = False
        try:
            r = raw_input()
            if r == "":
                termino = True
            else:
                r = r.split(" ")
                if len(r) != 3:
                    termino = True
                try:
                    r[0], r[1], r[2] = int(r[0]), int(r[1]), int(r[2])
                except ValueError:  # Si no son int's
                    termino = True

                if not r[0] in self.matriz.keys():
                    self.matriz[r[0]] = {}
                self.matriz[r[0]][r[1]] = r[2]

                if not r[1] in self.gamamenos.keys():
                    self.gamamenos[r[1]] = []
                self.gamamenos[r[1]].append(r[0])

        except EOFError:
            # Para manejar un EOF en caso de redirección de entrada.
            termino = True
        if termino:
            self.flujo = Flujo(copy.deepcopy(self.matriz))
            return 0
        return 1

    def aumentar_flujo(self):
        """Construye un camino aumentante, lo agrega al flujo y devuelve 1.
        Si no puede construir uno devuleve 0. Imprime el camino de acuerdo a
        la verbosidad"""
        camino = Camino_aumentante()
        while not camino.camino_vacio() and not camino.esta_t:
            x = camino.elemento()
            self._forward_search(x, camino)
            self._backward_search(x, camino)
            camino.quitar()

        if camino.esta_t:
            self.flujo.aumentar(camino)
            if self.__imprimir_verb([1, 11, 101, 111]):
                print "Incremento en el camino aumentante " + \
                    str(self.flujo.nroincremento) + ": " + str(camino.valor)
            if self.__imprimir_verb([2, 12, 102, 112]):
                print "camino aumentante " + \
                                    str(self.flujo.nroincremento) + ":"

                print camino.imprimir_camino() + ": " + \
                            str(camino.camino_valor())
            return 1

        else:
            if self.__imprimir_verb([0, 1, 2, 10, 11, 12]):
                print "No hay mas caminos aumentantes.\n"
            if self.__imprimir_verb([100, 101, 110, 111, 112]):
                print "No hay mas caminos aumentantes.\n"
                print "Corte Minimal: S = " + str(camino.imprimir_corte())
                print "Capacidad: " + str(self._capacidad_corte(camino))
            return 0

    def imprimir_flujo_maximal(self):
        if self.__imprimir_verb([10, 11, 12, 110, 111, 112]):
            print "Flujo Maximal:"
            for i in self.matriz.keys():
                for j in self.matriz[i].keys():
                    print "Lado " + str(i) + "," + str(j) + \
                                    ": " + str(self._flujo_mandado(i, j))

        print "Valor del flujo maximal : " + str(self.flujo.flujo_maximal())

# -------------------Funciones Auxiliares-----------------------
    def _forward_search(self, x, camino):
        """Agrega al camino todos los vecinos hacia adelante de x que puedan
        recibir más flujo y que no estén ya en el mismo.

        >>> ek = EstadoEK(0)
        >>> ek.matriz = {0:{2:1, 3:5, 4:30, 5:10, 6:20}, \
            2:{7:18}, 3:{8:4, 9:1}, \
            4:{2:17, 10:20, 9:20}, \
            5:{9:8, 10:1, 11:20}, \
            6:{9:2, 10:16, 11:7}, \
            7:{1:10}, 8:{10:5}, 9:{1:25}, 10:{1:15}, 11:{1:7}}
        >>> lados = {0:{2:0, 3:2, 4:0, 5:0, 6:0}, \
            2:{7:1}, 3:{8:2, 9:0}, \
            4:{2:1, 10:20, 9:6}, \
            5:{9:0, 10:1, 11:5}, \
            6:{9:0, 10:3, 11:2}, \
            7:{1:3}, 8:{10:1}, 9:{1:0}, 10:{1:0}, 11:{1:0} \
            }
        >>> ek.flujo = Flujo(lados)
        >>> camino = Camino_aumentante()
        >>> ek._forward_search(S, camino)
        >>> camino.cola
        [(0, -1, 65536, 1), (3, 0, 2, 1)]
        """
        for q in self._gamma_mas(x):
            if not camino.esta_en_cola(q):
                if self.flujo.capSobrante(x, q) > 0:
                    camino.add(q, self.flujo.capSobrante(x, q), FORW)

    def _backward_search(self, x, camino):
        """Agrega al camino todos los vecinos hacia atrás de x que le hayan
        enviado flujo y que no estén ya en el mismo.

        >>> ek = EstadoEK(0)
        >>> ek.matriz = {0:{2:1, 3:5, 4:30, 5:10, 6:20}, \
            2:{7:18}, 3:{8:4, 9:1}, \
            4:{2:17, 10:20, 9:20}, \
            5:{9:8, 10:1, 11:20}, \
            6:{9:2, 10:16, 11:7}, \
            7:{1:10}, 8:{10:5}, 9:{1:25}, 10:{1:15}, 11:{1:7}}
        >>> lados = {0:{2:0, 3:2, 4:0, 5:0, 6:0}, \
            2:{7:1}, 3:{8:2, 9:0}, \
            4:{2:1, 10:20, 9:6}, \
            5:{9:0, 10:1, 11:5}, \
            6:{9:0, 10:3, 11:2}, \
            7:{1:3}, 8:{10:1}, 9:{1:0}, 10:{1:0}, 11:{1:0} \
            }
        >>> ek.flujo = Flujo(lados)
        >>> camino = Camino_aumentante()
        >>> ek._forward_search(S, camino)
        >>> ek._backward_search(S, camino)
        >>> camino.cola
        [(0, -1, 65536, 1), (3, 0, 2, 1)]
        >>> camino.quitar()
        >>> ek._forward_search(camino.elemento(), camino)
        >>> camino.cola
        [(0, -1, 65536, 1), (3, 0, 2, 1), (8, 1, 2, 1)]
        >>> ek._backward_search(camino.elemento(), camino)
        >>> camino.quitar()
        >>> ek._forward_search(camino.elemento(), camino)
        >>> ek._backward_search(camino.elemento(), camino)
        >>> camino.quitar()
        >>> ek._forward_search(camino.elemento(), camino)
        >>> ek._backward_search(camino.elemento(), camino)
        >>> camino.cola
        [(0, -1, 65536, 1), (3, 0, 2, 1), (8, 1, 2, 1), (10, 2, 1, 1), \
        (6, 3, 1, -1)]
        """
        for q in self._gamma_menos(x):
            if not camino.esta_en_cola(q):
                if self._flujo_mandado(q, x) > 0:
                    camino.add(q, self._flujo_mandado(q, x), BACK)

    def _gamma_mas(self, x):
        """Retorna la lista de los vecinos hacia adelante de x.

        >>> ek = EstadoEK(0)
        >>> ek.matriz = {0:{2:0, 3:2, 4:0, 5:0, 6:0}, \
            2:{7:1}, 3:{8:2, 9:0}, \
            4:{2:1, 10:20, 9:6}, \
            5:{9:0, 10:1, 11:5}, \
            6:{9:0, 10:3, 11:2}, \
            7:{1:3}, 8:{10:1}, 9:{1:0}, 10:{1:0}, 11:{1:0} \
            }
        >>> ek._gamma_mas(0)
        [2, 3, 4, 5, 6]
        >>> ek._gamma_mas(1)
        []
        """
        try:
            return self.matriz[x].keys()
        except KeyError:
            return []

    def _gamma_menos(self, x):
        """Retorna la lista con los vecinos hacia atrás de x.

        >>> ek = EstadoEK(0)
        >>> ek.matriz = {0:{2:0, 3:2, 4:0, 5:0, 6:0}, \
            2:{7:1}, 3:{8:2, 9:0}, \
            4:{2:1, 10:20, 9:6}, \
            5:{9:0, 10:1, 11:5}, \
            6:{9:0, 10:3, 11:2}, \
            7:{1:3}, 8:{10:1}, 9:{1:0}, 10:{1:0}, 11:{1:0} \
            }
        >>> ek._gamma_menos(0)
        []
        >>> ek._gamma_menos(1)
        [7, 9, 10, 11]
        """
        try:
            return self.gamamenos[x]
        except KeyError:
            return []

    def _capTotal(self, x, y):
        """Devuelve la capacidad que tiene al principio el lado xy"""
        return self.matriz[x][y]

    def _flujo_mandado(self, x, y):
        """Lo de mandado es redundante, pero es mejor como para no
        confundir con flujo.py y esas cosas. Esto es el flujo total mandado.
        >>> ek = EstadoEK(0)
        >>> ek.matriz = {0:{2:1, 3:5, 4:30, 5:10, 6:20}, \
            2:{7:18}, 3:{8:4, 9:1}, \
            4:{2:17, 10:20, 9:20}, \
            5:{9:8, 10:1, 11:20}, \
            6:{9:2, 10:16, 11:7}, \
            7:{1:10}, 8:{10:5}, 9:{1:25}, 10:{1:15}, 11:{1:7}}
        >>> lados = {0:{2:0, 3:2, 4:0, 5:0, 6:0}, \
            2:{7:1}, 3:{8:2, 9:0}, \
            4:{2:1, 10:20, 9:6}, \
            5:{9:0, 10:1, 11:5}, \
            6:{9:0, 10:3, 11:2}, \
            7:{1:3}, 8:{10:1}, 9:{1:0}, 10:{1:0}, 11:{1:0} \
            }
        >>> ek.flujo = Flujo(lados)
        >>> ek._flujo_mandado(0, 4)
        30
        >>> ek._flujo_mandado(4, 10)
        0
        >>> ek._flujo_mandado(4, 2)
        16
        """
        return self._capTotal(x, y) - self.flujo.capSobrante(x, y)

    def _capacidad_corte(self, camino):
        """Devuelve la capacidad del corte del camino especificado. Para esto
        suma las capacidades de los lados con un vértice en el corte y otro
        fuera del mismo.

        >>> ek = EstadoEK(0)
        >>> ek.matriz = {0:{2:1, 3:5, 4:30, 5:10, 6:20}, \
            2:{7:18}, 3:{8:4, 9:1}, \
            4:{2:17, 10:20, 9:20}, \
            5:{9:8, 10:1, 11:20}, \
            6:{9:2, 10:16, 11:7}, \
            7:{1:10}, 8:{10:5}, 9:{1:25}, 10:{1:15}, 11:{1:7}}
        >>> camino1 = Camino_aumentante()
        >>> camino1.add(2, 1, FORW)
        >>> camino1.add(3, 5, FORW)
        >>> corte = camino1.devolver_corte()
        >>> print corte
        [0, 2, 3]
        >>> ek._capacidad_corte(camino1)
        83
        """
        corte = camino.devolver_corte()
        res = 0
        for i in corte:
            for j in self.matriz[i].keys():
                if not j in corte:
                    res += self.matriz[i][j]
        return res

    # Verifica si el argumento verbosidad esta en la lista de permitidos
    def __verb_correcta(self, verb):
        if VERB_PERMITIDAS.count(verb) != 1:
            return False
        else:
            return True

    def __imprimir_verb(self, list_verb):
        assert isinstance(list_verb, list)
        if list_verb.count(self.verbosidad) != 1:
            return False
        else:
            return True


def _test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    _test()
